import functools

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        if len(nums)<3:return results
        nums.sort()
        target = 0
        for a in range(0, len(nums)-2):
            if a!=0 and nums[a]==nums[a-1]:continue
            sa = nums[a]
            if sa+nums[a+1]+nums[a+2]>target:break
            if sa+nums[-1]+nums[-2]<target:continue
            for b in range(a+1, len(nums)-1):
                if b!=a+1 and nums[b]==nums[b-1]:continue
                sab = sa + nums[b]
                if sab+nums[b+1]>target:break
                if sab+nums[-1]<target:continue
                for c in range(b+1, len(nums)):
                    if c!=b+1 and nums[c]==nums[c-1]:continue
                    sabc = sab + nums[c]
                    if sabc>target:break
                    if sabc==target:
                        results.append([nums[a], nums[b], nums[c]])
        return results

print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))